package com.yulongtian.offers.day202209.day20220923;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/?favorite=xb9nqhhg
 *
 * @author YulongTian
 * @date 2022/9/23 - 13:01
 */
public class Test02 {
    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABCB";
        System.out.println(exist(board, word));
    }

    static boolean flag = false;

    public static boolean exist(char[][] board, String word) {

        if(board.length==1&&board[0].length==1){
            if(word.length()>1){
                return false;
            }
            return board[0][0]==word.charAt(0);
        }

        flag = false;
        Stack<Character> stack = new Stack<>();
        Stack<Character> target = new Stack<>();
        for (int i = 0; i < word.length(); i++) {
            target.push(word.charAt(i));
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int[][] path = new int[board.length][board[0].length];
                dfs(path, i, j, board, word, target, stack);
                if (flag) {
                    return flag;
                }
            }
        }

        return flag;
    }

    public static void dfs(int[][] path, int cur_i, int cur_j, char[][] board, String word, Stack<Character> target, Stack<Character> stack) {
        if (word.length() < stack.size()) {
            return;
        }
        if(path[cur_i][cur_j]==1){
            return;
        }
        if (word.length() == stack.size()) {
            if (stack.equals(target)) {
                flag = true;
            }
            return;
        }

        if (word.charAt(stack.size()) == board[cur_i][cur_j]) {
            path[cur_i][cur_j]=1;
            //上
            if (cur_i - 1 >= 0) {
                stack.push(word.charAt(stack.size()));
                dfs(path,cur_i - 1, cur_j, board, word, target, stack);
                stack.pop();
            }
            //右
            if (cur_j + 1 < board[0].length) {
                stack.push(word.charAt(stack.size()));
                dfs(path,cur_i, cur_j + 1, board, word, target, stack);
                stack.pop();
            }

            //下
            if (cur_i + 1 < board.length) {
                stack.push(word.charAt(stack.size()));
                dfs(path,cur_i + 1, cur_j, board, word, target, stack);
                stack.pop();
            }
            //左
            if (cur_j - 1 >= 0) {
                stack.push(word.charAt(stack.size()));
                dfs(path,cur_i, cur_j - 1, board, word, target, stack);
                stack.pop();
            }
        } else {
            return;
        }
    }
}
